Lesson 16 - Linked Lists

Example Program

//If you are not sure what some lines of code do, try looking back at
//previous example programs, notes, or ask a question.

#include <iostream>

using namespace std;

// Forward declare the LinkedList class for the node to use
class LinkedList;

// Example node class for linked lists
class node {
	// Parametrized constructor
	node(int v, node* n = NULL);
	// Destructor
	~node();

	// Data members. Note that one part is the data held in the node,
	// and one part is a pointer (or link) to the next node in the list
	int value;
	node* next;

	// We only want our list class to use nodes, so we can make the node
	// constructor private, and have the list class as a friend
	friend class LinkedList;

	// We also need the list insertion operator to be a friend of the node
	// class so it can retrieve values from nodes in the list.
	friend ostream& operator<<(ostream& out, const LinkedList& src);
};

// Example singly-circularly linked list class
// values will be added and removed at the "head" of the list, 
// making this technically a stack. We'll learn more about those later
class LinkedList {
public:
	// Default constructor
	LinkedList();
	// Desctructor
	~LinkedList();

	// Example manipulation functions
	void addValue(int value);
	int removeValue();

	// You'd usually have several more functions here, but for the purposes
	// of this example only the essential few have been shown

	// Output operator
	friend ostream& operator<<(ostream& out, const LinkedList& src);

private:
	node* head;
};

node::node(int v, node* n) {
	value = v;
	next = n;
}

node::~node() {

}

LinkedList::LinkedList() {
	// Start with no nodes
	head = NULL;
}

// Clear all nodes (delete memory)
LinkedList::~LinkedList() {
	// While we still have nodes in the list
	while(head) {
		// Store a pointer to the next node 
		node* temp = head->next;
		// Delete the current head node
		delete head;
		// Set the head node to the next node.
		// Note that when we get to the end of the list, this will
		// make head NULL, stopping this loop.
		head = temp;
	}
}

void LinkedList::addValue(int value) {
	// Here we create a new node with the new value and "head" as the next node
	// and set head to point to it. This inserts the new node at the start of the list,
	// as it will be the new head, and point to the previous head node. Note that if
	// head was NULL, the new node will have NULL as the next node, signifying that it's
	// the last node in the list.
	head = new node(value,head);
}

int LinkedList::removeValue() {
	int result = 0;
	// Check that we have at least one node
	if(head) {
		// Get result
		result = head->value;
		// Store a pointer to the next node
		node* temp = head->next;
		// Delete the head node
		delete head;
		// Set the head to the next node. If we just removed the last node, head will
		// be set to NULL, signifying that the list is empty.
		head = temp;
	}
	return result;
}

// Operator to output the list graphically
ostream& operator<<(ostream& out, const LinkedList& src) {
	// Declare temp pointer to iterate through the list
	node* temp = src.head;
	// Iterate through the list
	while(temp) {
		out << temp->value;
		// Write an arrow if there is another node
		if(temp->next) {
			out << " -> ";
		}

		// Move the next node
		temp = temp->next;
	}

	// Return out for chaining
	return out;
}

int main() {
	// Test our list class
	
	LinkedList l1;
	cout << "List 1: " << l1 << endl;

	for(int index = 0; index < 10; index++) {
		l1.addValue(index);
	}

	cout << "List 1: " << l1 << endl;

	l1.removeValue();
	l1.removeValue();
	l1.removeValue();

	cout << "List 1: " << l1 << endl;

	system("pause");
	return 0;	
}

Linked Lists

Linked lists are another important concept, as they are in the implementation of many data structures, in a variety of situations. As of yet, we’ve only used arrays to store collections of data. A linked list is another way to store data, but with a different set of advantages and disadvantages.

The main advantage of linked lists compared to arrays is that they have no set limit on capacity—the size can grow and shrink dynamically when data is added and removed. Conversely, to change the size of an array, one must reallocate, copy, and delete the array. Further, a linked list does not need to allocate a contiguous block of memory like an array does—making it much faster to initially construct.

However, there is also a significant disadvantage to linked lists: to access the data within them, your program must traverse a number of pointers. On the other hand, arrays, because they are stored in a contiguous block of memory, can retrieve data at any index in a short, constant amount of time.

Note — diagrams will be very helpful this lesson.

Nodes

The basic component of a linked list is what’s called a node. A node is what it sounds like: it represents one item of the list and includes one piece of data. A node has two parts: the data and one or more pointers to other nodes.

Links

The pointer sections of the nodes are what constitute the “links” of a linked list. Each node is linked to the next in the list by storing its address. With several nodes, the links create a chain. In this situation, if you don’t have access to the first node in the chain, you are not able to access one or more nodes. When you’re creating a linked list, you should always store a pointer to the “head,” or first node to prevent losing nodes and hence leaking memory.

Adding and Removing Nodes

That’s pretty much the entire basic concept of linked lists—though there are other types of linked lists that add more complications.

The fundamental operations on a linked list are, of course, adding and removing nodes. Suppose we have a “cursor” pointer to some node in our list. Adding a node after the cursor is extremely simple: have the new node point to the node after the cursor (newNode->next = cursor->next), then have the cursor point to your new node (cursor->next = new node). Removing a node after the cursor is similarly simple.

Remember that these examples are only one instance of an operation. Always consider the possible initial states of your list when implementing an operation, so that you don't, for example, accidentally try to delete off the end of the list. Image what you would need to do if you want to remove a node, but your cursor is pointing to the last node in your list.

These example operations are assuming a singly linked list.

Inserting a Node after the Cursor:

Removing a Node after the Cursor:

Again, there are many more situations than shown here. For example, what if you wanted to remove the node that the cursor is pointing to? What if you want to insert a node before the cursor? There are too many possibilities to go into great detail here—you can figure out what to do on your own.

Diagramming is extremely helpful! Drawing out processes like the ones above can make linked lists easy and intuitive to deal with.

Clearing Nodes

Here's another example list operation: clearing all nodes. At some point, you’re always going to want to clear your linked list (destructor, etc.), and you don’t want to leak memory when doing so. Again, diagramming the process is a great idea.

Repeat this process to remove all nodes.

Programming Exercises

Create your own data structure using a circularly, singularly linked list.

This will be a “List” data structure: it uses a “cursor” pointer with member functions to traverse and modify the list. You should make sure that all of your member functions account for each possible state of the list—e.g. do something different if the list is empty vs if it has nodes.

Members:

list() - default constructor
list(list) - copy constructor
~list() - destructor
next() – move cursor forward one node
prev() – move cursor back one node
get() – get the value of the node at the cursor
set(value) – set the value of the node at the cursor
insert(value) – insert a new node at the cursor with a value
remove() – remove a node at the cursor
operator<< – output the list
operator= – assign one list to another

Example Program

Download Run this Code

//If you are not sure what some lines of code do, try looking back at
//previous example programs, notes, or ask a question.

#include <iostream>

using namespace std;

// Forward declare the LinkedList class for the node to use
class LinkedList;

// Example node class for linked lists
class node {
	// Parametrized constructor
	node(int v, node* n = NULL);
	// Destructor
	~node();

	// Data members. Note that one part is the data held in the node,
	// and one part is a pointer (or link) to the next node in the list
	int value;
	node* next;

	// We only want our list class to use nodes, so we can make the node
	// constructor private, and have the list class as a friend
	friend class LinkedList;

	// We also need the list insertion operator to be a friend of the node
	// class so it can retrieve values from nodes in the list.
	friend ostream& operator<<(ostream& out, const LinkedList& src);
};

// Example singly-circularly linked list class
// values will be added and removed at the "head" of the list, 
// making this technically a stack. We'll learn more about those later
class LinkedList {
public:
	// Default constructor
	LinkedList();
	// Desctructor
	~LinkedList();

	// Example manipulation functions
	void addValue(int value);
	int removeValue();

	// You'd usually have several more functions here, but for the purposes
	// of this example only the essential few have been shown

	// Output operator
	friend ostream& operator<<(ostream& out, const LinkedList& src);

private:
	node* head;
};

node::node(int v, node* n) {
	value = v;
	next = n;
}

node::~node() {

}

LinkedList::LinkedList() {
	// Start with no nodes
	head = NULL;
}

// Clear all nodes (delete memory)
LinkedList::~LinkedList() {
	// While we still have nodes in the list
	while(head) {
		// Store a pointer to the next node 
		node* temp = head->next;
		// Delete the current head node
		delete head;
		// Set the head node to the next node.
		// Note that when we get to the end of the list, this will
		// make head NULL, stopping this loop.
		head = temp;
	}
}

void LinkedList::addValue(int value) {
	// Here we create a new node with the new value and "head" as the next node
	// and set head to point to it. This inserts the new node at the start of the list,
	// as it will be the new head, and point to the previous head node. Note that if
	// head was NULL, the new node will have NULL as the next node, signifying that it's
	// the last node in the list.
	head = new node(value,head);
}

int LinkedList::removeValue() {
	int result = 0;
	// Check that we have at least one node
	if(head) {
		// Get result
		result = head->value;
		// Store a pointer to the next node
		node* temp = head->next;
		// Delete the head node
		delete head;
		// Set the head to the next node. If we just removed the last node, head will
		// be set to NULL, signifying that the list is empty.
		head = temp;
	}
	return result;
}

// Operator to output the list graphically
ostream& operator<<(ostream& out, const LinkedList& src) {
	// Declare temp pointer to iterate through the list
	node* temp = src.head;
	// Iterate through the list
	while(temp) {
		out << temp->value;
		// Write an arrow if there is another node
		if(temp->next) {
			out << " -> ";
		}

		// Move the next node
		temp = temp->next;
	}

	// Return out for chaining
	return out;
}

int main() {
	// Test our list class
	
	LinkedList l1;
	cout << "List 1: " << l1 << endl;

	for(int index = 0; index < 10; index++) {
		l1.addValue(index);
	}

	cout << "List 1: " << l1 << endl;

	l1.removeValue();
	l1.removeValue();
	l1.removeValue();

	cout << "List 1: " << l1 << endl;

	system("pause");
	return 0;	
}

Lesson 16 - Linked Lists

Linked Lists

Nodes

Links

Adding and Removing Nodes

Clearing Nodes

Other Types of Linked Lists

Singly Linked

Circularly Linked

Doubly Linked

Trees

Programming Exercises